package OJAnswer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Objects;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-10-12
 * Time: 20:28
 */
public class Answer {
    //27.移除数组元素

    /**
     *
     * @param nums 目标数组
     * @param val 需要移除的元素
     * @return 返回新数组长度大小
     */
    public int removeElement(int[] nums, int val) {
        //定义快慢指针，fast指针指向新数组元素，slow指针表示新数组元素的位置
        int slow = 0;
        int fast = 0;
        for (; fast < nums.length; fast++) {
            if(nums[fast] != val){
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }

    //26.删除有序数组中的重复项

    /**
     *
     * @param nums 目标数组
     * @return 新数组长度大小
     */
    public int removeDuplicates(int[] nums) {
        //定义双指针slow,fast指针
        //fast指针用来获取新数组元素，即不等于当前slow指针指向的值的元素
        //slow指针指向的是当前新数组有效元素下标的最大值
        int slow = 0;
        int fast = 1;
        for (;fast < nums.length ; fast++) {
            if(nums[fast] != nums[slow]){//找到不重复的元素值
                nums[slow + 1] = nums[fast];
                slow++;
            }
        }
        return slow + 1;
    }

    //977.有序数组的平方

    /**
     *
     * @param nums 目标数组
     * @return 新数组
     */
    public int[] sortedSquares(int[] nums) {
        //定义左右指针
        int left = 0;
        int right  =nums.length - 1;
        int[] newArray = new int[nums.length];
        int count = nums.length - 1;
        while(left <= right){
            int pow1 = nums[left] * nums[left];
            int pow2 = nums[right] * nums[right];
            if(pow1 < pow2){
                newArray[count--] = pow2;
                right--;
            }else{
                newArray[count--] = pow1;
                left++;
            }
        }
        return newArray;
    }

    //283.移除零

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     */
    public void moveZeroes(int[] nums) {
        //fast指针遍历数组，用来获取非零元素
        //slow指针用来表示非零元素下次交换元素的下标位置
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if(nums[fast] != 0){
                //找到非零值，与nums[slow]交换值
                swap(nums,slow++,fast);
            }
        }
    }

    private void swap(int[] nums,int slow, int fast) {
        int temp = nums[slow];
        nums[slow] = nums[fast];
        nums[fast] = temp;
    }

    //76.最小覆盖子串

    /**
     * (滑动窗口 + 双指针)
     * 时间复杂度: O(N)
     * 空间复杂度: O(N)
     * @param ss
     * @param tt
     * @return 最小覆盖子串
     */
    public String minWindow(String ss, String tt) {
        //定义left,right指针
        int left = 0;
        int right = 0;

        //返回的字符串
        String ret = "";

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();

        //统计t字符串的字符个数
        for (char ch:t) {
            map2.put(ch,map2.getOrDefault(ch,0) + 1);
        }

        int minLen = Integer.MAX_VALUE;//更新的窗口长度最小值
        int count = 0;//记录窗口的自字符种类个数

        for (; right < s.length; right++) {
            //map2中包含该字符,对应在map1中的字符个数+1
            if(map2.containsKey(s[right])){
                map1.put(s[right],map1.getOrDefault(s[right],0) + 1);
                if(Objects.equals(map2.get(s[right]), map1.get(s[right]))){
                    count++;
                }
                //判断是否符合窗口定义
                while(count == map2.size()){
                    //更新minLen
                    if(minLen > right - left + 1){
                        minLen = right - left + 1;
                        ret = ss.substring(left,right + 1);
                    }

                    //符合缩小窗口左边界
                    if(map2.containsKey(s[left]) && Objects.equals(map2.get(s[left]), map1.get(s[left]))){
                        count--;
                    }
                    map1.put(s[left],map1.getOrDefault(s[left],0) - 1);
                    left++;
                }
            }
        }
        return ret;
    }

    //水果成蓝

    /**
     *
     * @param nums 目标数组
     * @return 最大子区间长度
     */
    public int totalFruit(int[] nums) {
       //定义双指针
       int left = 0;
       int right = 0;

       //更新最大值
       int maxLen = 0;

       //记录窗口内整数的出现次数
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (; right < nums.length; right++) {

            map.put(nums[right],map.getOrDefault(nums[right],0) + 1);

            //移动left指针，让窗口变回合法状态
            while(map.size() == 3){
                map.put(nums[left],map.getOrDefault(nums[left],0) - 1);

                //判断当前整数的是否value == 0
                if(map.get(nums[left]) == 0){
                    map.remove(nums[left]);
                }

                left++;
            }

            //更新最大值
            if(map.size() < 3) maxLen = Math.max(maxLen,right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] array = {3,2,2,3};
        Answer answer = new Answer();
        int newLen = answer.removeElement(array,3);
        for (int i = 0; i < newLen; i++) {
            System.out.print(array[i] + " ");
        }

        System.out.println();

        int[] array1 = {0,0,1,1,1,2,2,3,3,4};
        newLen = answer.removeDuplicates(array1);
        for (int i = 0; i < newLen; i++) {
            System.out.print(array1[i] + " ");
        }

        System.out.println();

        int[] array2 = {-4,-1,0,3,10};
        int[] ret = answer.sortedSquares(array2);
        System.out.println(Arrays.toString(ret));

        int[] array3 = new int[]{0,1,0,3,12};
        answer.moveZeroes(array3);
        System.out.println(Arrays.toString(array3));


        String ss = "cabwefgewcwaefgcf";
        String tt = "cae";
        String ret1 = answer.minWindow(ss,tt);
        System.out.println(ret1);

        int[] array4 = {3,3,3,1,2,1,1,2,3,3,4};
        int ret2 = answer.totalFruit(array4);
        System.out.println(ret2);

    }
}
